public class CanCompleteCircuit {

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        /**
         * gas油站  cost可加多少升
         * 1.设置一个变量记录当前油量
         * 2.记录一个起始点
         * 3.设置一个数组记录点位是否被当作过起始点
         * 3.判断当前油量是否能够到达下一个，如果不能则重新设置起始点

         */
        int currentGas=0;
        int start=0;
        while (start<gas.length){
            currentGas=gas[start]-cost[start];
            if(currentGas<0){
                start++;
                continue;
            }
            int end=(start+1)%gas.length;
            while (true){
                currentGas=(currentGas+gas[end])-cost[end];
                if(currentGas<0){
                    break;
                }
                end=(end+1)%gas.length;
                if(end==start){
                    return start;
                }
            }
            start++;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] gas =new int[]{1,2,3,4,5};
        int[] cost=new int[]{3,4,5,1,2};
       /* int[] gas =new int[]{2,3,4};
        int[] cost=new int[]{3,4,3};*/
        System.out.println(canCompleteCircuit(gas,cost));
    }
}
